<template>
    <div class="demo-collapse">
        <el-collapse v-model="activeNames" @change="handleChange">
            <el-collapse-item title="解题思路" name="thinking">
                <div>
                    <div>
                        Dijkstra算法算法思路是设置一个集合S记录已求得的最短路径的顶点，初始时把源点V0（图中的某个顶点）放入S，
                        集合S每并入一个新顶点Vi，都要修改源点V0到集合 V-S 中顶点当前的最短路径长度值。
                    </div>
                    <div>
                        在构造过程中需要两个辅助数组：
                    </div>
                    <div>
                        dist[ ] ：记录从源点V0到其他各顶点当前的最短路径长度，它的初态为：若从 V0 到 Vi有直接路径（即V0 和 Vi
                        邻接），则dist[ i ]为这两个顶点边上的权值；否则置 dist[ i ] 为 ∞。
                    </div>
                    <div>
                        path[ ]：path[ i ]表示从源点到顶点 i 之间的最短路径的前驱结点。在算法结束时，
                        可以根据其值追溯到源点 V0 到 Vi的最短路径。
                    </div>
                    <div>
                        假设从顶点 V0 = 0出发，邻接矩阵Edge表示带权无向图，Edge[i][j]表示无向边 (i, j)的权值，
                        若不存在无向边(i, j)，则Edge[i][j]为 ∞。
                    </div>
                    <div>
                        <strong>Dijkstra算法步骤如下：</strong>
                    </div>
                    <div>
                        1）初始化：集合S初始化为{0}，dist[ ] 的初始值dist[i] = Edge[0][i]，path[ ]的初始值path[i] = -1，i = 1,2,...,n-1。
                    </div>
                    <div>
                        2）从顶点集合 V - S中选出Vj，满足dist[j] = Min{dist[i] | Vi∈V - S}，
                        Vj就是当前求的一条从 V0 出发的最短路径的终点，令S = S∪{j}。
                    </div>
                    <div>
                        修改从V0出发到集合 V - S上任一顶点Vk可达的最短路径长度：若dist[j] + Edge[j][k] &lt; dist[k]，
                        则更新 dist[k] = dist[j] + Edge[j][k]，并修改path[k] = j（即修改顶点Vk的最短路径的前驱结点 ）。
                    </div>
                    <div>
                        4）重复 2）~  3）操作共 n-1 次，直到所有的顶点都包含在 S 中。
                    </div>
                </div>
            </el-collapse-item>
            <el-collapse-item title="代码实现" name="code">
                <div v-highlight>
                    <div>C/C++:</div>
                    <pre class="language-javascript">
                      <code>
                        #include &lt;iostream>
                            #include &lt;vector>
                            using namespace std;
                             
                            const int INF = 1e9; // int范围约为 (-2.15e9, 2.15e9)
                             
                            /*Dijkstra算法解决的是单源最短路径问题，即给定图G(V,E)和起点s(起点又称为源点),边的权值为非负，
                            求从起点s到达其它顶点的最短距离，并将最短距离存储在矩阵d中*/
                            void Dijkstra(int n, int s, vector&lt;vector&lt;int>> G, vector&lt;bool> &vis, vector&lt;int> &d, vector&lt;int> &pre)
                            {
                                /*
                                 *   n:        顶点个数
                                 *   s:        源点
                                 *   G:        图的邻接矩阵
                                 * vis:        标记顶点是否已被访问
                                 *   d:        存储源点s到达其它顶点的最短距离
                                 * pre:        最短路径中v的前驱结点
                                 */
                             
                                // 初始化
                                fill(vis.begin(), vis.end(), false);
                                fill(d.begin(), d.end(), INF);
                                d[s] = 0;
                                for (int i = 0; i &lt; n; ++i)
                                {
                                    pre[i] = i;
                                }
                             
                                // n次循环,确定d[n]数组
                                for (int i = 0; i &lt; n; ++i)
                                {
                                    // 找到距离s最近的点u,和最短距离d[u]
                                    int u = -1;
                                    int MIN = INF;
                                    for (int j = 0; j &lt; n; ++j)
                                    {
                                        if (!vis[j] && d[j] &lt; MIN)
                                        {
                                            u = j;
                                            MIN = d[j];
                                        }
                                    }
                             
                                    // 找不到小于INF的d[u],说明剩下的顶点与起点s不连通
                                    if (u == -1)
                                    {
                                        return;
                                    }
                             
                                    vis[u] = true;
                                    for (int v = 0; v &lt; n; ++v)
                                    {
                                        // 遍历所有顶点，如果v未被访问 && 可以达到v && 以u为中介点使d[v]更小
                                        if (!vis[v] && G[u][v] != INF && d[u] + G[u][v] &lt; d[v])
                                        {
                                            d[v] = d[u] + G[u][v];   // 更新d[v]
                                            pre[v] = u;              // 记录v的前驱顶点为u（新添加）
                                        }
                                    }
                                }
                            }
                             
                            // 输出从起点s到顶点v的最短路径
                            void DFSPrint(int s, int v, vector&lt;int> pre)
                            {
                                if (v == s)
                                {
                                    cout &lt;&lt; s &lt;&lt; " ";
                                    return;
                                }
                                DFSPrint(s, pre[v], pre);
                                cout &lt;&lt; v &lt;&lt; " ";
                            }
                             
                             
                            int main()
                            {
                                int n = 6;
                                /*邻接矩阵*/
                                vector&lt;vector&lt;int>> G = {
                                                         {  0,  4,INF,INF,  1,  2},
                                                         {  4,  0,  6,INF,INF,  3},
                                                         {INF,  6,  0,  6,INF,  5},
                                                         {INF,INF,  6,  0,  4,  5},
                                                         {  1,INF,INF,  4,  0,  3},
                                                         {  2,  3,  5,  5,  3,  0}
                                                        };
                                vector&lt;bool> vis(n);
                                vector&lt;int> d(n);
                                vector&lt;int> pre(n);
                             
                                Dijkstra(n, 0, G, vis, d, pre);
                             
                                for (size_t i = 0; i &lt; d.size(); ++i)
                                {
                                    cout &lt;&lt; "the shortest path " &lt;&lt; i &lt;&lt; " is: " &lt;&lt; d[i] &lt;&lt; endl;
                                }
                                cout &lt;&lt; endl;
                             
                                // v = 2: 0->5->2  cost = 2 + 5 = 7
                                // v = 3: 0->4->3  cost = 1 + 4 = 5
                                int v = 2;
                                DFSPrint(0, v, pre);
                                cout &lt;&lt; endl &lt;&lt; "cost = " &lt;&lt; d[v] &lt;&lt; endl;
                             
                                return 0;
                            }   
                      </code>
                    </pre>
                </div>
                <div v-highlight>
                    <div>Python:</div>
                    <pre class="language-javascript">
                        <code>
                            import numpy as np
                            from numpy import inf
                            from operator import itemgetter
                            import copy
 
 
                            #初始化各个节点的关联节点及其对应的距离
                            #其中A~G分别对应数字1~7
                            node_dist=[[1,[2,6,7],[12,16,14]],
                                    [2,[1,3,6],[12,10,7]],
                                    [3,[2,4,5,6],[10,3,5,6]],
                                    [4,[3,5],[3,4]],
                                    [5,[3,4,6,7],[5,4,2,8]],
                                    [6,[1,2,3,5,7],[16,7,6,2,9]],
                                    [7,[1,5,6],[14,8,9]]]
 
                            #以D为起点，A为终点，寻找全局最优路径
                            #其中S为已经找到最短路径的节点集合+对应的最短路径值；U为尚未找到最短路径的节点集合+当前的最短值
                            S = [[4,0]]  #S集合初始化
                            U = [[1, inf],
                            [2, inf],
                            [3, 3],
                            [5, 4],
                            [6, inf],
                            [7, inf]] #U集合初始化
 
                            path_opt = [[4,[4]]]#最优路径初始化
                            path_temp = [[1,[]],
                                        [2,[]],
                                        [3,[4,3]],
                                        [5,[4,5]],
                                        [6,[]],
                                        [7,[]]]#其他当前路径初始化
 
                            for r in range(len(U)):
                                print(r)
    
                                U0 = [i[0] for i in U]
                                U1 = [i[1] for i in U]
                                min_index, min_number = min(enumerate(U1), key=itemgetter(1))
                                dist_index = U0[min_index]-1  #选出节点  对应node_dist的索引l
    
                                path_opt.append(path_temp[min_index])#将该节点对应的路径加入最优
                                path_temp.remove(path_temp[min_index])#从临时路径中删除已确定最优路径的节点
    
                                #将节点添加到S集中 + 从U集中删除
                                S.append([U0[min_index],min_number])
                                U.remove(U[min_index])
    
                                print(S)
                            #     print(path_opt)
    
                                U0_new = [i[0] for i in U]
                                U1_new = [i[1] for i in U]
    
                                #更新U集中对应的距离
                                x = node_dist[dist_index][1]
                                #判断是否更新 
                                for temp_index,w in enumerate(x):
                                    temp_distance = inf
                                    if w in [s[0] for s in S]:
                                        pass
                                    else:
                                        temp_distance = min_number+node_dist[dist_index][2][temp_index]  #新距离
                                        #先找旧的在新U中的index
                                        old_index = U0_new.index(w)
                                        #查找“旧”距离
                                        old_distance = U1_new[old_index]
                                        #判断是否更新路径值
                                        if temp_distance &lt; old_distance:
                                            U[old_index][1] = temp_distance
                                            #更新临时距离
                                            d=copy.deepcopy(path_opt[-1][1])
                                            d.append(path_temp[old_index][0])
                                            path_temp[old_index][1] = d
                            #                 print(path_temp)
                                        else:
                                            pass
                                print(U)
                        </code>
                    </pre>
                </div>
                <div v-highlight>
                    <div>Java:</div>
                    <pre class="language-javascript">
                      <code>
                        public class DijstraAlgorithm {
                            //不能设置为Integer.MAX_VALUE，否则两个Integer.MAX_VALUE相加会溢出导致出现负权
                            public static int MaxValue = 100000;
                            
                            public static void main(String[] args) {
                                Scanner input = new Scanner(System.in);
                                System.out.println("请输入顶点数和边数:");
                                //顶点数
                                int vertex = input.nextInt();
                                //边数
                                int edge = input.nextInt();
                         
                                int[][] matrix = new int[vertex][vertex];
                                //初始化邻接矩阵
                                for (int i = 0; i &lt; vertex; i++) {
                                    for (int j = 0; j &lt; vertex; j++) {
                                        matrix[i][j] = MaxValue;
                                    }
                                }
                                for (int i = 0; i &lt; edge; i++) {
                                    System.out.println("请输入第" + (i + 1) + "条边与其权值:");
                                    int source = input.nextInt();
                                    int target = input.nextInt();
                                    int weight = input.nextInt();
                                    matrix[source][target] = weight;
                                }
                         
                                //单源最短路径，源点
                                int source = input.nextInt();
                                //调用dijstra算法计算最短路径
                                dijstra(matrix, source);
                            }
                         
                            public static void dijstra(int[][] matrix, int source) {
                                //最短路径长度
                                int[] shortest = new int[matrix.length];
                                //判断该点的最短路径是否求出
                                int[] visited = new int[matrix.length];
                                //存储输出路径
                                String[] path = new String[matrix.length];
                         
                                //初始化输出路径
                                for (int i = 0; i &lt; matrix.length; i++) {
                                    path[i] = new String(source + "->" + i);
                                }
                         
                                //初始化源节点
                                shortest[source] = 0;
                                visited[source] = 1;
                         
                                for (int i = 1; i &lt; matrix.length; i++) {
                                    int min = Integer.MAX_VALUE;
                                    int index = -1;
                         
                                    for (int j = 0; j &lt; matrix.length; j++) {
                                        //已经求出最短路径的节点不需要再加入计算并判断加入节点后是否存在更短路径
                                        if (visited[j] == 0 && matrix[source][j] &lt; min) {
                                            min = matrix[source][j];
                                            index = j;
                                        }
                                    }
                         
                                    //更新最短路径
                                    shortest[index] = min;
                                    visited[index] = 1;
                         
                                    //更新从index跳到其它节点的较短路径
                                    for (int m = 0; m &lt; matrix.length; m++) {
                                        if (visited[m] == 0 && matrix[source][index] + matrix[index][m] &lt; matrix[source][m]) {
                                            matrix[source][m] = matrix[source][index] + matrix[index][m];
                                            path[m] = path[index] + "->" + m;
                                        }
                                    }
                         
                                }
                         
                                //打印最短路径
                                for (int i = 0; i &lt; matrix.length; i++) {
                                    if (i != source) {
                                        if (shortest[i] == MaxValue) {
                                            System.out.println(source + "到" + i + "不可达");
                                        } else {
                                            System.out.println(source + "到" + i + "的最短路径为：" + path[i] + "，最短距离是：" + shortest[i]);
                                        }
                                    }
                                }
                            }
                        }
                      </code>
                    </pre>
                </div>
            </el-collapse-item>
        </el-collapse>
    </div>
</template>

<script lang="ts" setup>
import { ref } from 'vue'
const activeNames = ref(['thinking'])
const handleChange = (val: string[]) => {
    console.log(val)
}
// 代码实现部分
import "vue-code-highlight/themes/prism-solarizedlight.css";
import "vue-code-highlight/themes/window.css";

</script>
